﻿#include "PolygonAlg.h"
#include <iostream>

void PolygonAlg::run() {
	
	vector<Point>& points = *m_points;
	vector<vector<Line>>& liness = *m_polyLines;	// 多组折线
	vector<vector<vector<Line>>>& polygonss = *m_polygonss;	// 多组多边形

	bool successed;
	 //1.哈密顿路径问题
	vector<Line> res;
	successed = fun1(points, res);
	liness.clear();
    liness.push_back(res);

	// 2.线段偏移问题
	//vector<Line> lines = liness[0];
	//successed = fun2(lines, 5);
	//liness.clear();
	//liness.push_back(lines);

	
}

// 1.旅行商问题 - 哈密顿路径算法
bool PolygonAlg::fun1(vector<Point>& points, vector<Line>& path) {
	// 将所有的Point对象连接起来，形成首尾相连的线段，并使路径尽可能短
	
	// 检查点的数量是否足够
	if (points.size() < 2) {
		return false; // 至少需要两个点才能形成线段
	}
	
	// 清空结果容器
	path.clear();
	
	// 如果只有两个点，直接连接它们
	if (points.size() == 2) {
		path.push_back(Line(points[0], points[1]));
		path.push_back(Line(points[1], points[0])); // 回到起点
		return true;
	}
	
	// 使用最近邻算法构建初始路径
	vector<int> tour; // 存储点的访问顺序
	vector<bool> visited(points.size(), false);
	
	// 从第一个点开始
	tour.push_back(0);
	visited[0] = true;
	
	// 贪心策略：每次选择距离当前点最近的未访问点
	while (tour.size() < points.size()) {
		int last = tour.back();
		int next = -1;
		double minDist = DoubleMaxNumValue;
		
		for (size_t i = 0; i < points.size(); ++i) {
			if (!visited[i]) {
				// 计算距离
				Point vec = points[i] - points[last];
				double dist = vec.vecLength();
				
				if (dist < minDist) {
					minDist = dist;
					next = i;
				}
			}
		}
		
		if (next != -1) {
			tour.push_back(next);
			visited[next] = true;
		}
		else {
			// 理论上不应该到达这里，除非有孤立的点
			return false;
		}
	}
	
	// 应用2-opt优化来改进路径
	bool improved = true;
	int maxIterations = 100; // 限制迭代次数
	int iterations = 0;
	
	while (improved && iterations < maxIterations) {
		improved = false;
		iterations++;
		
		// 尝试交换路径中的两条边，看是否能减少总长度
		for (size_t i = 0; i < tour.size() - 2; ++i) {
			for (size_t j = i + 2; j < tour.size(); ++j) {
				// 避免形成无效的交换
				if (j == tour.size() - 1 && i == 0) continue;
				
				// 计算当前路径的两条边的长度
				int i1 = tour[i];
				int i2 = tour[i + 1];
				int j1 = tour[j];
				int j2 = tour[(j + 1) % tour.size()];
				
				Point vec1 = points[i2] - points[i1];
				Point vec2 = points[j2] - points[j1];
				double oldDist = vec1.vecLength() + vec2.vecLength();
				
				// 计算交换后的两条边的长度
				Point newVec1 = points[j1] - points[i1];
				Point newVec2 = points[j2] - points[i2];
				double newDist = newVec1.vecLength() + newVec2.vecLength();
				
				// 如果交换后路径更短，则进行交换
				if (newDist < oldDist) {
					// 反转从i+1到j的部分
					reverse(tour.begin() + i + 1, tour.begin() + j + 1);
					improved = true;
					break;
				}
			}
			if (improved) break;
		}
	}
	
	// 根据优化后的访问顺序构建路径
	for (size_t i = 0; i < tour.size(); ++i) {
		int current = tour[i];
		int next = tour[(i + 1) % tour.size()];
		path.push_back(Line(points[current], points[next]));
	}
	
	return true;
}
// 2.向上偏移
// 2.向上偏移
bool PolygonAlg::fun2(vector<Line>& path, double offset) {
	if (path.empty() || offset <= 0) {
		return false;
	}

	try {
		// 遍历每条线段，计算法向量并进行偏移
		for (auto& line : path) {
			// 获取线段的方向向量
			Point direction = line.Pt2 - line.Pt1;

			// 计算法向量（垂直于方向向量，向上）
			// 向上的法向量：(-dy, dx)
			Point normal(-direction.y, direction.x);

			// 单位化法向量
			normal = normal.normalizeVec();

			// 按照偏移量缩放法向量
			Point offsetVector = normal * offset;

			// 对线段的起点和终点进行偏移
			line.Pt1 = line.Pt1 + offsetVector;
			line.Pt2 = line.Pt2 + offsetVector;
		}

		return true;
	}
	catch (const std::exception& e) {
		// 处理可能的异常
		std::cerr << "Error in fun2: " << e.what() << std::endl;
		return false;
	}
}

// 3.两侧法向偏移，允许交叉
bool PolygonAlg::fun3(vector<Line>& path, double offset) {

	return true;
}

// 4.两侧法相偏移，消除交叉
bool PolygonAlg::fun4(vector<Line>& path, double offset) {

	return true;
}